<head>
    <meta charset="UTF-8">
<title>算法训练 Rains Over Atlantis</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p><br />
大雨无情地侵蚀着亚特兰蒂斯的土地，并终将毁灭它。为了组织人民撤离，你想知道亚特兰蒂斯多快就会毁灭殆尽。</p>
<p>你有一幅亚特兰蒂斯的地图。地图是一个矩形的网格，每个格子里有一个整数表示该位置海拔为多少米。网格外面是大海，海拔为零。所有为海拔零的格子都是水域，所有海拔大于零的格子都是陆地，没有海拔小于零的区域。</p>
<p>如果两个格子有公共边，水就能从高的格子流向低的格子。如果两个有公共边的格子一样高，水能向任意一边流。</p>
<p>因为雨非常大，所以如果一个格子里的水流不走，就会积在那里，直到水平面足够高使其得以流走。地图外面的大海可以接收任意多的水。举个例子，比如下面这幅地图：</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=edRa4Dj3" width="90" height="62" alt="" /></p>
<p>低洼地区会积水。我们把积水地区的海拔加上水深称为<span style="color: rgb(255, 0, 0);">水平面</span>，上面地图的水平面将会是：</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=4A98gr8j" width="93" height="65" alt="" /></p>
<p>注意中间地域的0，尽管它是水域，因为它不与外界相连，所以它也会积水。边界上的0与外界相连，所以来自8的水可以经它流走。</p>
<p>水流动的方向决定于水平面的高低。如果与一个区域相邻（有公共边）有若干个区域的水平面都比它低，那么它的水就会流向其中最低的一个。如果最低的也有多个，流向哪里没有所谓，这在下文会提到。</p>
<p>现在流水侵蚀开始了。每天，一个格子被侵蚀掉多少&mdash;&mdash;海拔降低多少&mdash;&mdash;决定于水怎么流过它。如果水从S流到与S相邻的T，那么S的海拔将降低min(S的水平面-T的水平面,M)。所有的侵蚀都在同一时间&mdash;&mdash;一天结束的时候&mdash;&mdash;发生。例如，M=5时，上面的地图描绘的土地就会被侵蚀成下面这个样子：</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=7ytJT2he" width="87" height="59" alt="" /></p>
<p>一天的侵蚀过后，多余的水会流走：当一片区域的水平面高于与它相邻的区域的水平面时，水就会从高处流到低处，直到两个区域水面相平。水依然回像第一天那样积累。第二天，水平面变成：</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=B9Jejydb" width="88" height="62" alt="" /></p>
<p>又过了一天的侵蚀，地图又变成下面这样：</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=rTTMm4M9" width="90" height="57" alt="" /></p>
<p>&hellip;&hellip;这时亚特兰蒂斯的居民就要紧急疏散了。你的任务是计算要过多少天亚特兰蒂斯的海拔高度会全变成0。</p>
<p><br />
【输入格式】<br />
第一行读入一个整数T，表示接下来有T组数据。</p>
<p>每组数据由包含三个整数H、W、M的一行开始，这三个整数分别表示地图的长、宽和一天最大的侵蚀高度。</p>
<p>接下来H行每行W个整数，其中的第i行第j个数表示地图中(i,j)格子的高度。<br />
【输出格式】<br />
对于每组测试数据，输出一行&ldquo;Case #x: y&rdquo;（不包含引号），其中x表示测试数据的编号，y表示多少天就能侵蚀完整个亚特兰蒂斯。<br />
【样例输入】</p>
<p>2</p>
<p>3 6 5</p>
<p>5 9 9 9 9 9</p>
<p>0 8 9 0 2 5</p>
<p>3 9 9 9 9 9</p>
<p>3 6 3</p>
<p>3 8 10 11 10 8</p>
<p>7 5 2 12 8 8</p>
<p>6 9 11 9 8 4</p>
<p>【样例输出】</p>
<p>Case #1: 3</p>
<p>Case #2: 5</p>
<p>【数据规模和约定】</p>
<p>共20个测试点，每个点5分。<span class="Apple-tab-span" style="white-space:pre">		</span></p>
<p>测试点1~4：1&le;T&le;10, 1&le;H,W&le;10, 1&le;M&le;100, 0&le;所有海拔&le;100。</p>
<p>测试点5~8：1&le;T&le;50, 1&le;H,W&le;20, 1&le;M&le;100, 0&le;所有海拔&le;100。</p>
<p>测试点9~20：1&le;T&le;10, 1&le;H,W&le;20, 1&le;M&le;10^15, 0&le;所有海拔&le;10^15。</p>